#include"SLT.h"

SLTNode* BuySLTNode(SLTdatatype x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc failed");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SLTPushHead(SLTNode** pphead, SLTdatatype x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = (*pphead);
	(*pphead) = newnode;
}

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

void SLTPushBack(SLTNode** pphead, SLTdatatype x)
{
	SLTNode* newnode = BuySLTNode(x);
	if ((*pphead) == NULL)
	{
		(*pphead) = newnode;
	}
	else
	{
		SLTNode* tail = (*pphead);
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}


void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free((*pphead));
	(*pphead) = next;

}

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free((*pphead));
		(*pphead) = NULL;
	}
	else
	{
		SLTNode* tail = (*pphead);
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

SLTNode* SLTFind(SLTNode* phead, SLTdatatype x)
{
	assert(phead);
	SLTNode* tmp = phead;
	while (tmp->data != x)
	{
		tmp = tmp->next;
	}
	if (tmp)
	{
		return tmp;
	}
	else
	{
		return NULL;
	}
}
void SLTPosBackPop(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next -> next;
	free(pos->next);
	pos->next = next;
}

void SLTPopPos(SLTNode* pos)
{
	assert(pos);
	assert(pos->next);
	SLTNode* next = pos->next;
	while (next->next != NULL)
	{
		pos->data = next->data;
		next = next->next;
		pos = pos->next;
	}
	pos->data = next->data;
	free(next);
	pos->next = NULL;
}

void SLTDestory(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		SLTNode* Del = cur;
		cur = cur->next;
		free(Del);
	}
}


struct SLTNode* mergeTwoLists(struct SLTNode* list1, struct SLTNode* list2)
{
	struct SLTNode* tail1 = list1;
	struct SLTNode* tail2 = list2;
	struct SLTNode* newList = NULL;
	struct SLTNode* newtail = NULL;
	while (tail1 != NULL && tail2 != NULL)
	{
		if (tail1->data < tail2->data)
		{
			if (newList == NULL)
			{
				newList = tail1;
				newtail = tail1;
			}
			else
			{
				newtail->next = tail1;
				newtail = tail1;
			}
			tail1 = tail1->next;
		}
		else
		{
			if (newList == NULL)
			{
				newList = tail2;
				newtail = tail2;
			}
			else
			{
				newtail->next = tail2;
				newtail = tail2;
			}
			tail2 = tail2->next;
		}

	}
	if (tail1 != NULL)
	{
		newtail->next = tail1;
		newtail = tail1;
		tail1 = tail1->next;
	}
	if (tail2 != NULL)
	{
		newtail->next = tail2;
		newtail = tail2;
		tail2 = tail2->next;
	}
	return newList;
}